/*
题目描述：矩阵中的路径
设计一个函数，判断一个矩阵中是否存在一条包含字符串所有字符串的路径。
分析：
采用回溯法，路径可以看成一个栈，使用布尔矩阵来判断是否已经走过这段路径
 */
public class E12 {
    public static void main(String[] args){
        Character[][] matrix = {{'a','b','t','g'}
                              ,{'c','f','c','s'}
                              ,{'j','d','e','h'}
                            };
        Character[] str1 = {'b','f','c','e'};
        Character[] str2 = {'a','b','f','b'};

        boolean res1 = hasPath(matrix, 3,4, str1);
        boolean res2 = hasPath(matrix, 3,4,str2);

        System.out.println(res1);
        System.out.println(res2);

    }

    public static boolean hasPath(Character[][] matrix, int rows, int cols, Character[] str){
        if(matrix == null || rows < 1 || cols < 1 || str == null){
            return false;
        }
        Boolean[][] visited = new Boolean[matrix.length][matrix[0].length];

        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                visited[i][j] = false;
            }
        }

        Integer pathLen = 0;
        for(int row = 0; row < rows; row ++){
            for(int col = 0; col < cols; col ++){
                if(hasPathCore(matrix, rows, cols, row, col, str, pathLen, visited)){
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean hasPathCore(final Character[][] matrix, int rows, int cols, int row, int col
                                      , final Character[] str, Integer pathLen, Boolean[][] visited){
        if(pathLen == str.length){
            return true;
        }
        boolean hasPath = false;
        if(row >= 0 && row <= rows && col >= 0 && col <= cols
            && matrix[row][col] == str[pathLen]
            && !visited[row][col]){
            pathLen ++;
            visited[row][col] = true;
            hasPath = hasPathCore(matrix, rows, cols, row, col - 1, str, pathLen,visited)
                        || hasPathCore(matrix, rows, cols, row, col + 1, str, pathLen, visited)
                        || hasPathCore(matrix, rows, cols, row + 1, col, str, pathLen, visited)
                        || hasPathCore(matrix, rows, cols, row - 1, col, str, pathLen, visited);

            if(!hasPath){
                pathLen --;
                visited[row][col] = false;
            }
        }
        return hasPath;
    }
}
/*
true
false
 */
